package LC19;

/**
 * 删除链表的倒数第n个节点
 */

class Solution {

    //方法1  递归求解
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode s = new ListNode(-1, head);  //哨兵节点  解决数组只有一位时head.next = null的情况
        recursion(s,n);  //利用哨兵去移除元素  然后返回哨兵的下一个节点
        return s.next;  // 返回哨兵的下一个节点也就是原先链表的头
    }

    private int recursion(ListNode p, int n) {
        if (p == null) {  //最后一个节点的下一个为null也就是倒数第0个
            return 0;
        }
        int nth = recursion(p.next, n);  //下一个节点是倒数第几位
        if (nth == n) {  //当下一个节点是倒数第n个时
            p.next = p.next.next;  //移除节点
        }
        return nth + 1;  //返回当前节点是倒数第几位
    }

    //方法2
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode s = new ListNode(-1, head); //哨兵节点  解决下一个节点为空的情况
        if (s.next == null) {
            return null;
        }
        ListNode p1 = s;  //要留下
        ListNode p2 = s;  //要远走
        while (n + 1 != 0) {  //使p2和p1保持n+1的距离
            n--;
            p2 = p2.next;
        }
        while (p2 != null) {  //p2走到null的时候p1就在要删除的节点的前一个位置
            p1 = p1.next;
            p2 = p2.next;
        }
        p1.next = p1.next.next;  //删除
        return s.next;
     }

}
